package web

import (
	"fmt"
	"regexp"
	"strings"
)

type router struct {
	// trees 是按照 HTTP 方法来组织的
	// 如 GET => *node
	trees map[string]*node
}

func newRouter() router {
	return router{
		trees: map[string]*node{},
	}
}

// addRoute 注册路由。
// method 是 HTTP 方法
// - [x] 已经注册了的路由，无法被覆盖。例如 /user/home 注册两次，会冲突
// - [x] path 必须以 / 开始并且结尾不能有 /，中间也不允许有连续的 /
// - [x] 不能在同一个位置注册不同的参数路由，例如 /user/:id 和 /user/:name 冲突
// - [x] 不能在同一个位置同时注册通配符路由和参数路由，例如 /user/:id 和 /user/* 冲突
// - 同名路径参数，在路由匹配的时候，值会被覆盖。例如 /user/:id/abc/:id，那么 /user/123/abc/456 最终 id = 456
func (r *router) addRoute(method string, path string, handler HandleFunc) {

	root, isExist := r.trees[method]
	if !isExist {
		root = &node{
			path: "/",
			typ:  nodeTypeStatic,
		}
		r.trees[method] = root
	}

	if path == "" {
		panic("web: 路由是空字符串")
	}
	if len(path) > 0 && path[0] != '/' {
		panic("web: 路由必须以 / 开头")
	}
	if path != "/" && path[len(path)-1] == '/' {
		panic("web: 路由不能以 / 结尾")
	}

	if path == "/" {
		if root.handler != nil {
			panic(fmt.Sprintf("web: 路由冲突[%s]", path))
		}
		root.handler = handler
		return
	}

	segs := strings.Split(path[1:], "/")
	for _, seg := range segs {
		if seg == "" {
			panic(fmt.Sprintf("web: 非法路由。不允许使用 //a/b, /a//b 之类的路由, [%s]", path))
		}
		child := root.childOrCreate(seg)
		root = child
	}

	if root.handler != nil {
		panic(fmt.Sprintf("web: 路由冲突[%s]", path))
	}
	root.handler = handler
}

// findRoute 查找对应的节点
// 注意，返回的 node 内部 HandleFunc 不为 nil 才算是注册了路由
func (r *router) findRoute(method string, path string) (*matchInfo, bool) {
	root, exist := r.trees[method]
	if !exist {
		return &matchInfo{n: nil}, false
	}

	if path == "/" {
		return &matchInfo{n: root}, true
	}

	var lastStarNode *node = nil // 记录匹配的通配符node
	var pathParams map[string]string
	segs := strings.Split(path[1:], "/")
	for _, seg := range segs {
		node, matchParams, match := root.childOf(seg)
		if !match {
			if lastStarNode != nil { // 通配符匹配多段
				root = lastStarNode
				break
			}
			return &matchInfo{n: nil}, false
		}
		if match && node.typ == nodeTypeAny { // 通配符匹配
			lastStarNode = node
		}
		if matchParams != nil { // 正则或路径匹配
			if pathParams == nil {
				pathParams = map[string]string{}
			}
			for k, v := range matchParams {
				pathParams[k] = v
			}
		}
		root = node
	}
	m := &matchInfo{
		n:          root,
		pathParams: pathParams,
	}
	return m, true
}

type nodeType int

const (
	// 静态路由
	nodeTypeStatic = iota
	// 正则路由
	nodeTypeReg
	// 路径参数路由
	nodeTypeParam
	// 通配符路由
	nodeTypeAny
)

// node 代表路由树的节点
// 路由树的匹配顺序是：
// 1. 静态完全匹配
// 2. 正则匹配，形式 :param_name(reg_expr)
// 3. 路径参数匹配：形式 :param_name
// 4. 通配符匹配：*
// 这是不回溯匹配
type node struct {
	typ nodeType

	path string
	// children 子节点
	// 子节点的 path => node
	children map[string]*node
	// handler 命中路由之后执行的逻辑
	handler HandleFunc

	// 通配符 * 表达的节点，任意匹配
	starChild *node

	paramChild *node
	// 正则路由和参数路由都会使用这个字段
	paramName string

	// 正则表达式
	regChild *node
	regExpr  *regexp.Regexp
}

// child 返回子节点
// 第一个返回值 *node 是命中的节点
// 第二个返回值 表示命中的正则或路径参数后, 捕获的 key, value
// 第三个返回值 bool 代表是否命中
func (n *node) childOf(path string) (*node, map[string]string, bool) {

	var matchParams map[string]string = nil

	if path == "" {
		return nil, matchParams, false
	}
	// 先静态匹配, 再匹配正则, 路径参数, 通配符

	if n.children != nil {
		findNode, findIt := n.children[path]
		if findIt {
			return findNode, matchParams, true
		}
	}
	// regexp
	if n.regChild != nil {
		subMatch := n.regChild.regExpr.FindStringSubmatch(path)
		if subMatch != nil { // 匹配
			matchParams = map[string]string{
				n.regChild.paramName: subMatch[0],
			}
			return n.regChild, matchParams, true
		}
	}

	if n.paramChild != nil {
		matchParams = map[string]string{
			n.paramChild.paramName: path,
		}
		return n.paramChild, matchParams, true
	}

	if n.starChild != nil {
		return n.starChild, matchParams, true
	}

	return nil, matchParams, false
}

// childOrCreate 查找子节点，
// 首先会判断 path 是不是通配符路径
// 其次判断 path 是不是参数路径，即以 : 开头的路径
// 最后会从 children 里面查找，
// 如果没有找到，那么会创建一个新的节点，并且保存在 node 里面
func (n *node) childOrCreate(path string) *node {
	if path == "" {
		return nil
	}

	if path[0] == ':' { // 参数路径 或 正则
		// eg: :id(.*)
		reg := regexp.MustCompile(`^:(\w+)\((.+)\)$`)
		subMatch := reg.FindStringSubmatch(path)
		if subMatch != nil { // 匹配, 为正则表达式
			if n.paramChild != nil {
				panic(fmt.Sprintf("web: 非法路由，已有路径参数路由。不允许同时注册正则路由和参数路由 [%s]", path))
			}
			if n.starChild != nil {
				panic(fmt.Sprintf("web: 非法路由，已有通配符路由。不允许同时注册通配符路由和正则路由 [%s]", path))
			}
			if n.regChild != nil && n.regChild.path != path {
				if n.regChild != nil {
					panic(fmt.Sprintf("web: 非法路由，已有正则路由[%s]。不允许重复注册正则路由 [%s]", n.regChild.path, path))
				}
			}
			if n.regChild == nil {
				n.regChild = &node{
					path:      path,
					typ:       nodeTypeReg,
					paramName: subMatch[1],                     // eg: "id"
					regExpr:   regexp.MustCompile(subMatch[2]), // eg: ".*"
				}
			}
			return n.regChild
		} else { // 不匹配, 为参数路径
			if n.regChild != nil {
				panic(fmt.Sprintf("web: 非法路由，已有正则路由。不允许同时注册正则路由和参数路由 [%s]", path))
			}
			if n.starChild != nil {
				panic(fmt.Sprintf("web: 非法路由，已有通配符路由。不允许同时注册通配符路由和参数路由 [%s]", path))
			}
			if n.paramChild != nil && n.paramChild.path != path {
				panic(fmt.Sprintf("web: 路由冲突，参数路由冲突，已有 %s，新注册 %s", n.paramChild.path, path))
			}
			if n.paramChild == nil {
				n.paramChild = &node{
					path:      path,
					paramName: path[1:],
					typ:       nodeTypeParam,
				}
			}
			return n.paramChild
		}
	}

	if path == "*" { // 通配符路径
		if n.paramChild != nil {
			panic(fmt.Sprintf("web: 非法路由，已有路径参数路由。不允许同时注册通配符路由和参数路由 [%s]", path))
		}
		if n.regChild != nil {
			panic(fmt.Sprintf("web: 非法路由，已有正则路由。不允许同时注册通配符路由和正则路由 [%s]", path))
		}
		if n.starChild == nil {
			n.starChild = &node{
				path: "*",
				typ:  nodeTypeAny,
			}
		}
		return n.starChild
	}

	if n.children == nil {
		n.children = map[string]*node{}
	}

	findNode, exist := n.children[path]
	if !exist {
		findNode = &node{
			path: path,
			typ:  nodeTypeStatic,
		}
		n.children[path] = findNode
	}
	return findNode
}

type matchInfo struct {
	n          *node
	pathParams map[string]string
}

func (m *matchInfo) addValue(key string, value string) {
	if m.pathParams == nil {
		// 大多数情况，参数路径只会有一段
		m.pathParams = map[string]string{key: value}
	}
	m.pathParams[key] = value
}
